package com.ch10;

import java.util.ArrayList;
import java.util.Arrays;
import java.util.List;
import java.util.Random;

/**
 * 根据坐标点查看是有有该点
 * @author Linxiaozhi
 *
 */
public class SearchPoint {
	int size = 200;
	int range = 2000;
	int[][] arr;

	int[][] generateArray() {
		int[][] arr = new int[size][size];
		Random rand = new Random(System.currentTimeMillis());
		int counter = range;
		int max = size * size;
		for (int i = 0; i < size; i++)
			for (int j = 0; j < size; j++) {
				if (rand.nextInt(max) < counter) {
					arr[i][j] = rand.nextInt(range);
					counter--;
				} else {
					arr[i][j] = -1;
				}
				max--;
			}
		//验证是否正确
		counter = 0;
		for (int i = 0; i < size; i++)
			for (int j = 0; j < size; j++) {
				if (arr[i][j] != -1)
					counter++;
			}
		System.out.println("counter:" + counter);
		return arr;
	}

	int search(int x, int y) {
		return arr[x][y];
	}

	static class Point {
		int y;
		int val;

		public Point(int y, int val) {
			super();
			this.y = y;
			this.val = val;
		}

	}

	int search2(int x, int y) {
		List[] lists = new List[size];
		for (int i = 0; i < size; i++) {
			for (int j = 0; j < size; j++) {
				if (arr[i][j] != -1) {
					if (lists[i] == null) {
						lists[i] = new ArrayList<Point>();
					}
					lists[i].add(new Point(j, arr[i][j]));
				}
			}
		}

		for (int i = 0; i < lists[x].size(); i++) {
			Point p = (Point) lists[x].get(i);
			if (p.y == y)
				return p.val;
		}
		return -1;
	}

	int search3(int x, int y) {
		int[] arrx = new int[size];
		int[] arry = new int[range];
		int[] arrval = new int[range];
		int counter = 0;
		for (int i = 0; i < size; i++) {
			arrx[i] = counter;
			for (int j = 0; j < size; j++) {
				if (arr[i][j] != -1) {
					arry[counter] = j;
					arrval[counter] = arr[i][j];
					counter++;
				}
			}
		}

		int high = x == size - 1 ? range : arrx[x + 1];
		for (int i = arrx[x]; i < high; i++) {
			if (arry[i] == y) {
				return arrval[i];
			}
		}

		return -1;
	}

	/**
	 * arry的数是按顺序排列的
	 * @param x
	 * @param y
	 * @return
	 */
	int search4(int x, int y) {
		int[] arrx = new int[size];
		int[] arry = new int[range];
		int[] arrval = new int[range];
		int counter = 0;
		for (int i = 0; i < size; i++) {
			arrx[i] = counter;
			int low = arrx[i];
			for (int j = 0; j < size; j++) {
				if (arr[i][j] != -1) {
//					arry[counter] = j;
//					arrval[counter] = arr[i][j];
//					counter++;

					int k = counter;
					arry[k] = j;
					arrval[k] = arr[i][j];
					int t = 0;
					while ((t = k - 1) >= low) {
						if (arry[t] <= arry[k])
							break;
						int temp = arry[t];
						arry[t] = arry[k];
						arry[k] = temp;
						temp = arrval[t];
						arrval[t] = arrval[k];
						arrval[k] = temp;
						k = t;
					}
					counter++;
				}
			}
		}

		int high = x == size - 1 ? range : arrx[x + 1];
//		for (int i = arrx[x]; i < high; i++) {
//			if (arry[i] == y) {
//				return arrval[i];
//			}
//		}

		int val = Arrays.binarySearch(arry, arrx[x], high, y);
		if (val >= arrx[x] && val <= high - 1) {
			return arrval[val];
		}
//System.out.println(Arrays.toString(arry));
		return -1;
	}

	public static void main(String[] args) {
		SearchPoint sp = new SearchPoint();
		sp.arr = sp.generateArray();
		for (int i = 0; i < 200; i++) {
			System.out.print(sp.search(i, i));
			System.out.print("    ");
			System.out.print(sp.search2(i, i));
			System.out.print("    ");
			System.out.print(sp.search3(i, i));
			System.out.print("    ");
			System.out.println(sp.search4(i, i));
		}
	}
}
